package com.atwulidun.iterativebinarysearch01;

import java.util.ArrayList;
import java.util.List;

public class IterativeBinarySearchDemo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 7, 7, 8, 8, 9, 9, 10};
        List<Integer> list = IterativeBinarySearch.binarySearch(arr, 9);
        System.out.println(list);
    }
}

// 传入的需要是一个有序数组
class IterativeBinarySearch {
    public static List<Integer> binarySearch(int[] arr, int val) {
        // 定义一个左边界变量
        int left = 0;
        // 定义一个右边界变量
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (val < arr[mid]) {
                right = mid - 1;
            } else if (val > arr[mid]) {
                left = mid + 1;
            } else {
                List<Integer> list = new ArrayList<>();
                int leftIndex = mid - 1;
                while (leftIndex >= 0 && arr[leftIndex] == val) {
                    list.add(leftIndex);
                    leftIndex--;
                }
                list.add(mid);
                int rightIndex = mid + 1;
                while (rightIndex < arr.length && arr[rightIndex] == val) {
                    list.add(rightIndex);
                    rightIndex++;
                }
                return list;
            }
        }
        return new ArrayList<>();
    }
}
